According to the virtualization technology using virtualization software such as VMware and Xen, it is possible to make one physical server to operate as a plurality of virtual severs. As a result, it becomes easier to streamline a server operation according to the situation (refer to Japanese Laid Open Patent Application JP-P2005-115653A). It is also possible by using the virtualization technology to achieve “server migration” easily. The server migration is exemplified as follows.
FIG. 1 conceptually shows “server consolidation” as one example of the server migration. As shown in FIG. 1, let us consider a case where existing five physical servers M1 to M5 are operating and these five physical servers M1 to M5 are consolidated into three high-performance physical servers M6 to M8. For example, the physical servers M1 and M2 are respectively replaced with virtual servers VM1 and VM2 which run on the physical server M6. Also, the physical server M3 is replaced with a virtual server VM3 which runs on the physical server M7. Moreover, the physical servers M4 and M5 are respectively replaced with virtual servers VM4 and VM5 which run on the physical server M8. In the example shown in FIG. 1, the five physical servers M1 to M5 constitute a “source server group”, while the three physical servers M6 to M8 constitute a “destination server group”. Such the server consolidation can reduce occupation space and electric power consumption due to the decrease in the number of physical servers, which greatly contributes to reduction of operation management costs.
FIG. 2 conceptually shows “server reallocation” as another example of the server migration. As shown in FIG. 2, let us consider a case where a server operation is carried out with virtual servers VM1 to VM5 which run on physical servers M1 to M3. In the daytime when load is increased, the virtual servers VM1 and VM2 are built on the physical server M1, the virtual servers VM3 and VM4 are built on the physical server M2, and the virtual server VM5 is built on the physical server M3. On the other hand, in the nighttime when load is decreased, the virtual servers VM1, VM2 and VM4 are built on the physical server M1, the virtual servers VM3 and VM5 are built on the physical server M2, and thus the physical server M3 is not used. In this manner, the number of physical servers used is reduced depending on the situation, which can reduce the operation management costs. In the example shown in FIG. 2, the virtual servers VM1 to VM5 in the daytime or the nighttime constitute a “source server group”, while the physical servers M1 to M3 constitute a “destination server group”.
As described above, the server migration is important from the viewpoint of the reduction of the operation management costs. In advance of the server migration, it is necessary not only to estimate the number of servers under the post-migration situation but also to prepare a “migration plan” that indicates “to which destination server, each source server is allocated”, i.e., an allocation relationship between the source servers and the destination servers. A fundamental condition that the migration plan should meet is an inclusion relation between computer resources. That is to say, the sum of “resource usage” of source servers which are to be allocated to a certain destination server must not exceed “resource capacity” of the certain destination server. Here, the computer resources include a CPU, disk, memory and network.
Also, a migration plan with which the number of servers under the post-migration situation becomes as small as possible is preferable from the viewpoint of the costs. When goods of various sizes are packed in bins with the same constant capacity, a problem of finding a minimum number of bins necessary for packing the set of goods is generally called a “Bin Packing Problem (BPP)”. With regard to the Bin Packing Problem, it is well known that to find an optimum solution within a practical time is extremely difficult. A “First-Fit-Decrease (FFD) algorithm” is known as an approximate solution algorithm (refer to “Combinatorial Optimization: Theory and Algorithms”, written by B. Korte and J. Vygen, translated by Takao Asano et al., Springer-Verlag Tokyo, Nov. 3, 2005, pp. 470-472).
A load balancing technique with respect to a parallel computer is described in Japanese Laid Open Patent Application JP-A-Heisei, 10-27167. The parallel computer consists of a plurality of computers and executes a parallel program composed of a plurality of constitutive programs. When the plurality of constitutive programs are allocated to the plurality of computers, the load balancing is performed in consideration of the load applied to the computer by the constitutive program itself. More specifically, a history collecting program collects resource utilization of each constitutive program. Moreover, a scheduler refers to current resource utilization of each computer and allocates a constitutive program with the larger resource utilization to a computer with the smaller current resource utilization. In other words, the scheduler allocates processing with a heavier load to a computer with a larger available capacity.